﻿using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.Hash
{
    //set数据结构
    //set数据结构相对于数组来说占用空间大，速度慢，set把数值映射到key上都要做hash计算

    class IntersectionOfArray
    {
        //====================== 力扣349 两个数组的交际
        //给定两个数组，编写一个函数啦计算它们的交集
        //输出结果中每个元素一定是唯一的
        //不需要考虑输出结果的顺序
        //输入：nums1 = [1,2,2,1],nums2 = [2,2]
        //输入：[2]
        public int[] Intersection(int[] nums1, int[] nums2)
        {
            if (nums1 == null || nums1.Length == 0 || nums2 == null || nums2.Length == 0)
                return new int[0];

            HashSet<int> set1 = new HashSet<int>();
            HashSet<int> resSet = new HashSet<int>();
            //遍历数组1
            foreach(int i in nums1)
            {
                set1.Add(i);
            }
            //遍历数组2的过程中判断哈希表中是否存在该元素
            foreach(int i in nums2)
            {
                if(set1.Contains(i))
                {
                    resSet.Add(i);
                }
            }

            int[] resArr = new int[resSet.Count];
            int index = 0;
            //将结果转换为数组
            foreach(int i in resSet)
            {
                resArr[index++] = i; 
            }
            return resArr;

        }

        //============================= 力扣250 两个数组的交集2
        //给定两个数组，编写一个函数来计算它们的交集
        //输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致
        //我们可以不考虑输出结果的顺序
        //输入：nums1 = [1,2,2,1],nums2 = [2,2]
        //输入：[2，2]
        public int[] Intersect(int[] nums1,int[] nums2)
        {//哈希表
            //时间复杂度：O(m+n) 两个数组都需要遍历
            //空间复杂度：O(min(m,n)) 哈希表大小不会超过较短数组的长度

            //保证numsl.length > nums2.length
            //为了降低空间复杂度，先遍历较短的数字并记录次数，然后遍历较长的数组得到交集
            if (nums1.Length > nums2.Length)
                return Intersect(nums2, nums1);

            //遍历第一个数组，并在哈希表中记录第一个数组中的每个数字以及对应出现的次数
            Hashtable hashtable = new Hashtable();
            foreach(int num in nums1)
            {
                int count = 0;
                if (hashtable.ContainsKey(num))
                {
                    count = (int)hashtable[num];
                    hashtable[num] = ++count;
                }else
                    hashtable.Add(num, ++count);
            }

            //遍历第二个数组
            //对于第二个数组中的每个数字，如果在哈希表中存在这个数字，则将该数字添加到答案，并减少哈希表中该数字出现的次数
            int[] intersection = new int[nums1.Length];
            int index = 0;
            foreach(int num in nums2)
            {
                if(hashtable.ContainsKey(num))
                {
                    intersection[index++] = num;
                    int count = (int)hashtable[num];
                    if(--count == 0)
                    {
                        hashtable.Remove(num);
                    }
                    else
                    {
                        hashtable[num] = count;
                    }
                }
            }
            int[] tempArr = new int[index];
            Array.Copy(intersection, tempArr, index);
            return tempArr;
        }
        public int[] Intersect_1(int[] nums1, int[] nums2)
        {//排序+双指针
            //如果两个数组是有序的，则可以使用双指针的方法得到两个数组的交集
            //时间复杂度：O(mlogm+nlogn) ,m和n是两个数组的长度，对两个数组排序的时间是O(mlogm + nlogn)，遍历两个数组的时间复杂度是O(m + n),所以总时间复杂度是O(mlogm + nlogn)
            //空间复杂度：O(min(m+n)

            Array.Sort(nums1);
            Array.Sort(nums2);

            int length1 = nums1.Length, length2 = nums2.Length;
            int[] intersection = new int[Math.Min(length1, length2)];
            //初始，两个指针分别指向两个数组的头部
            int index1 = 0, index2 = 0, index = 0;
            while(index1 < length1 && index2 < length2)
            {
                //每次比较两个指针指向的数字，如果不等，则将指向较小数字的指针右移一位
                //如果两个数字相等，则将该数字添加到答案，并将两个指针都右移一位。
                if(nums1[index1] < nums2[index2])
                {
                    index1++;
                }else if(nums1[index1] > nums2[index2])
                {
                    index2++;
                }
                else
                {
                    intersection[index] = nums1[index1];
                    index1++;
                    index2++;
                    index++;
                }
            }
            int[] tempArr = new int[index];
            Array.Copy(intersection, tempArr, index);
            return tempArr;


        }


    }
}
